\documentclass[E:/GsjzTle/main/main.tex]{subfiles}
\begin{document}

\begin{itemize}
\item
  当背包的最大容量很大的时候，常规的做法时间空间复杂度都会炸
\item
  但这类问题通常物品的价值或个数不会很大
\item
  定义 \(n\) 为物品的个数，\(V\) 为背包的容量，\(W\)
  为物品体积的上限，\(val\) 为物品价值的上限
\item
  \begin{enumerate}
  \def\labelenumi{\arabic{enumi}.}
  \item
    当 \(n\) 较小(\(300\))、\(V\) 很大(\(1e9\))、\(W\)
    很大(\(1e9\))、\(val\) 较小(\(300\))的时候：\\
    可以定义 \(f[i][j]\) 表示前 \(i\) 个物品选取的价值为 \(j\)
    时的最小体积\\
    那么只要取最大的 \(j\) 使得 \(f[n][j] <= V\) 即可\\
    复杂度为 \(O(n^2\times val)\)
  \item
    当 \(n\) 很小(\(40\))、\(V\) 很大(\(1e9\))、\(W\)
    很大(\(1e9\))、\(val\) 很大(\(1e9\))的时候：\\
    可以考虑折半枚举 \(+\) 二分查找\\
    把物品分为前 \(\dfrac{n}{2}\) 和后 \(\dfrac{n}{2}\) ，然后把前
    \(\dfrac{n}{2}\) 的状态保存下来并排序，记为 \(vec\)\\
    再枚举后\(\dfrac{n}{2}\)，计算当前状态的体积 \(v\)，然后再去 \(vec\)
    中二分查找 \(V-v\) 的最优解\\
    （\(vec\) 存储的是
    \(pair<weight , val>\)，\(vec[i].val = max(vec[0\sim i].val)\)）\\
    复杂度为
    \(O(2^{\dfrac{n}{2}}\times \log _{2}\left( \dfrac{n}{2}\right) )\)
  \item
    当 \(n\) 较大(\(2e5\))、\(V\) 较大(\(2e5\))、\(W\)
    较小\((100)\)、\(val\) 很大(\(1e9\))的时候：\\
    考虑分治 \(or\) 单调队列优化决策单调性\\
    复杂度为 \(O(W\times V\times \log{V})\)
  \item
    当 \(n\) 较大(\(2e5\))、\(V\) 较大(\(2e5\))、\(W\)
    较小\((100)\)、\(val\) 很大(\(1e9\))的时候：\\
    考虑一个骗分做法：\\
    先把 \(n\)
    个物品按照性价比排序，然后把性价比高的存入背包，使得背包容量 \(V\)
    不断减少，直到 \(O(n \times V)\) 的做法可以解决（骗分，慎用！）
  \end{enumerate}
\item
  一：

\begin{lstlisting}
signed main()
{
	int T = 1;
	cin >> T;
	while(T --)
	{
		memset(f , 0x3f , sizeof(f));
		f[0] = 0;
		int n , V , up = 0 , res = 0;
		cin >> n >> V;
		for(int i = 1 ; i <= n ; i ++) cin >> w[i] >> v[i] , up += v[i];
		for(int i = 1 ; i <= n ; i ++)
		{
			for(int j = up ; j >= v[i] ; j --) 
			{
				f[j] = min(f[j] , f[j - v[i]] + w[i]);
			}
		}
		for(int i = 0 ; i <= up ; i ++) if(f[i] <= V) res = i;
		cout << res << '\n';
	}
	return 0;
}
\end{lstlisting}
\item
  二：

\begin{lstlisting}
#define int long long
const ll INF (0x3f3f3f3f3f3f3f3fll);
const int N = 41;
int w[N] , v[N];
vector<pair<int , int>>vec;
signed main()
{
	int n , V;
	cin >> n >> V;
	rep(i , 1 , n) cin >> w[i] , v[i] = w[i]; 
	int m = n / 2 , res = 0;
	vec.push_back(make_pair(INF , INF));
	rep(i , 0 , (1 << m) - 1)
	{
		int weight = 0 , val = 0;
		rep(j , 0 , m - 1) if(i >> j & 1) weight += w[m - j] , val += v[m - j];
		vec.push_back(make_pair(weight , val));
	} 
	sort(vec.begin() , vec.end());
	int ma = -1;
	for(int i = 0 ; i < vec.size() ; i ++)
	{
		ma = max(ma , vec[i].second);
		vec[i].second = ma;
	}
	m = n - m;
	rep(i , 0 , (1 << m) - 1)
	{
		int weight = 0 , val = 0;
		rep(j , 0 , m - 1) if(i >> j & 1) weight += w[n - j] , val += v[n - j];
		if(weight > V) continue ;
		pair<int , int>p = make_pair(V - weight , INF);
		int pos = upper_bound(vec.begin() , vec.end() , p) - vec.begin();
		res = max(res , vec[pos - 1].second + val);
	}
	cout << res << '\n';
	return 0;
}
\end{lstlisting}
\item
  三：

\begin{lstlisting}
constexpr ll INF = 1e18;
void work(vector<ll> &a, vector<ll> &b, vector<ll> &c, int l, int r, int L, int R)
{
	if (l > r) return;
	int m = (l + r) / 2;
	int g = -1;
	ll val = -INF;
	for (int i = L; i <= R && i <= m; ++i)
	{
		ll v = a[i] + b[m - i];
		if (v > val)
		{
			val = v;
			g = i;
		}
	}
	c[m] = val;
	work(a, b, c, l, m - 1, L, g);
	work(a, b, c, m + 1, r, g, R);
}

void solve(int n, int m)
{
	vector<int> w(n), v(n);
	int ma = 0;
	for (int i = 0; i < n; ++i)
	{
		cin >> w[i] >> v[i];
		if (w[i] <= m) ma = max(ma, w[i]);
	}
	vector<vector<int>> vals(ma + 1);
	for (int i = 0; i < n; ++i)
	{
		if (w[i] <= m) vals[w[i]].push_back(v[i]);
	}
	vector<ll> ans(m + 1);
	for (int W = 1; W <= ma; ++W)
	{
		sort(vals[W].begin(), vals[W].end(), greater<int>());
		for (int b = 0; b < W; ++b)
		{
			int siz = (m - b) / W;
			vector<ll> a(siz + 1), c(siz + 1), d(siz + 1);
			for (int i = 0; i <= siz; ++i)
			{
				a[i] = ans[i * W + b];
			}
			for (int i = 0; i < siz; ++i)
			{
				c[i + 1] = c[i] + (i < int(vals[W].size()) ? vals[W][i] : 0);
			}
			work(a, c, d, 0, siz, 0, siz);
			for (int i = 0; i <= siz; ++i)
			{
				ans[i * W + b] = d[i];
			}
		}
	}
	cout << ans[m] << "\n";
}
signed main()
{
	int n, m;
	while (cin >> n >> m) solve(n, m);
	return 0;
}
\end{lstlisting}
\item
  四：

\begin{lstlisting}
const int N = 2e5 + 10 , M = 1e3 + 10;
struct node{
	int w , v;
}a[N];
long long f[M];
bool cmp(node a , node b)
{
	return 1ll * a.w * b.v < 1ll * b.w * a.v;
}
signed main()
{
	int n , m ;
	while(cin >> n >> m)
	{
		for(int i = 1 ; i <= n ; i ++) cin >> a[i].w >> a[i].v; 
		sort(a + 1 , a + 1 + n , cmp);
		long long ans = 0;
		int pos = 1;
		while(pos <= n && m >= 1000)
		{
			ans += a[pos].v;
			m -= a[pos].w;
			pos ++ ;
		}
		memset(f , 0 , (m + 1) << 3);
		for(int i = pos ; i <= n ; i ++)
		{
			for(int j = m ; j >= a[i].w ; j --)
				f[j] = max(f[j] , f[j - a[i].w] + a[i].v);
		}
		cout << ans + f[m] << '\n';
	}
	return 0;
}
\end{lstlisting}
\end{itemize}

\end{document}
